/*
实验8-2 最短路的交点
分数 30
作者 陈越
单位 浙江大学

给定有向加权图 G，和 4 个顶点 u, v, s, t。假设图 G 中所有边的权值都非负。设计一个算法来判定“从 u 到 v 的最短路径”和“从 s 到 t 的最短路径”是否存在一个交点 w。也即，顶点 w 是 u 到 v 的最短路径上的一个顶点，同时也是 s 到 t 的最短路径上的一个顶点。
注意：最短路径包含两个端点；一对顶点间的最短路径可能不止一条，求交点时必须将所有最短路径考虑在内。
输入格式：

输入第 1 行给出 6 个正整数，依次为：n（≤1000，图中顶点数）、m（≤3000，图中边数）、题面中描述的 4 个顶点 u, v, s, t 的编号。这里假设顶点从 1 到 n 编号，并且 u, v, s, t 的编号均不相同。
随后 m 行，每行给出一条有向边的起点编号、终点编号、非负权重（≤100）。题目保证每条边都不会重复给出，同行数字间以空格分隔。
输出格式：

在一行中，按编号递增的顺序输出所有交点。数字间以 1 个空格分隔，行首尾不得有多余空格。如果交点不存在，则在一行中输出 No Intersection。
输入样例 1：

6 7 1 2 3 4
1 2 3
1 5 1
3 5 1
5 6 1
5 4 2
6 4 1
6 2 1

输出样例 1：

5 6

输入样例 2：

4 4 1 2 3 4
1 2 1
3 4 1
1 4 1
3 2 1

输出样例 2：

No Intersection
*/

#include "../base/MGraph.cpp"

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <functional>
#include <algorithm>

using namespace std;

// 定义权重的最大值
#define MaxWeight 0x7FFF

// Dijkstra 算法, 有权图，路径权重在 edge 中，求 start 到 end 的多条最短路径
// paths：start 到 end 的多条最短路径
void Dijkstra(MGraph<int, int> &graph, vector<vector<int>> &paths, int start, int end) {
    int num_vertex = graph.get_num_vertex();
    vector<int> dist(num_vertex, MaxWeight); // 初始化距离数组
    vector<vector<int>> prev(num_vertex);                 // 前驱节点数组
    dist[start] = 0;                                      // 起点到起点的距离为0

    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>  pq;
    pq.push({0, start}); // 将起点加入优先队列

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u])
            continue; // 如果当前距离大于已知最短距离，跳过

        for (int v = 0; v < num_vertex; ++v) {
            if (graph.has_edge(u, v)) {
                int alt = dist[u] + graph.get_edge(u, v);
                if (alt < dist[v]) {
                    dist[v] = alt;
                    pq.push({alt, v});
                    prev[v].clear();
                    prev[v].push_back(u);
                } else if (alt == dist[v]) {
                    prev[v].push_back(u);
                }
            }
        }
    }

    vector<int> path;
    function<void(int)> dfs = [&](int u) {
        path.push_back(u);
        if (u == start) {
            reverse(path.begin(), path.end());
            paths.push_back(path);
            reverse(path.begin(), path.end());
        } else {
            for (int v : prev[u]) {
                dfs(v);
            }
        }
        path.pop_back();
    };

    dfs(end);
}


int main() {
    int n, m, u, v, s, t;
    cin >> n >> m >> u >> v >> s >> t;
    MGraph<int, int> graph(n, MaxWeight, true);
    for (int i = 0; i < m; ++i) {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        graph.add_edge(v1, v2, w);
    }
    // graph.print();

    vector<vector<int>> paths1, paths2;
    Dijkstra(graph, paths1, u, v);
    Dijkstra(graph, paths2, s, t);

    set<int> set1;
    for (int i = 0; i < paths1.size(); ++i) {
        for (int j = 0; j < paths1[i].size(); ++j) {
            set1.insert(paths1[i][j]);
        }
    }
    set<int> intersections;
    for (int i = 0; i < paths2.size(); ++i) {
        for (int j = 0; j < paths2[i].size(); ++j) {
            if (set1.find(paths2[i][j]) != set1.end()) {
                intersections.insert(paths2[i][j]);
            }
        }
    }

    if (intersections.empty()) {
        cout << "No Intersection" << endl;
    } else {
        bool first = true;
        for (auto it = intersections.begin(); it != intersections.end(); ++it) {
            if (!first) {
                cout << " ";
            }
            first = false;
            cout << *it;
        }
        cout << endl;
    }

    return 0;
}